/*
 * @lc app=leetcode.cn id=19 lang=java
 *
 * [19] 删除链表的倒数第N个节点
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    // 题目倒是提示了用双指针法.
    // java的链表貌似没有头指针，就是一开头一个空的指针
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 快慢指针法,快指针先走n步，然后慢指针走，最后慢指针到达的位置就是要删除的节点的前一个
        ListNode a = head , b = head;//a是快指针
        for(int i=0 ;i<n ;i++){
            a = a.next;
        }

        if(a == null){//因为题目保证n是有效的，即不超过链表长度的，所以可以直接删了第一个节点
            return head.next;//返回第二个节点
        }
        while(a.next!=null){
            a=a.next;
            b=b.next;
        }
        //这时候慢指针b停在要删除的节点前面
        b.next = b.next.next;
        
        return head;
    }
}
// @lc code=end

